package com.zhongge.doublelist;


/**
 * @ClassName MyLinkedList
 * @Description TODO 基于泛型的无头非循环双向链表(LinkedList底层)
 * @Author 笨忠
 * @Date 2025/8/10 19:13
 * @Version 1.0
 */
public class MyLinkedList<E> {
    //节点
    static class ListNode<E>{
        //数值域
        public E val;
        //前驱指针
        public ListNode<E> prev;
        //后继指针
        public ListNode<E> next;

        public ListNode(E val) {
            this.val = val;
        }
    }
    //头指针
    ListNode<E> head;
    //尾指针
    ListNode<E> last;

    /**
     * 头插
     * @param val
     */
    public void addFirst(E val) {
        //创建新节点
        ListNode<E> node = new ListNode<>(val);
        if (head == null) {
            head = last = node;
        } else {
            //先绑后
            node.next = head;
            head.prev = node;
            //头变新
            head = node;
        }
    }

    /**
     * 尾插
     * @param val
     */
    public void addLast(E val) {
        ListNode<E> node = new ListNode<>(val);
        if (head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }

    /**
     * 任意位置插入
     * @param index 索引
     * @param val 数值
     */
    public void addIndex(int index, E val) {
        //判断合法性
        int size = size();
        if (index < 0 || index > size) {
            System.out.println("索引不合法！！");
            return;
        }
        //头插
        if (index == 0) {
            addFirst(val);
            return;
        }
        //尾插
        if (index == size) {
            addLast(val);
            return;
        }
        //中间插
        //首先有一个节点
        ListNode<E> node = new ListNode<>(val);
        //找出当前索引所在的节点
        ListNode<E> cur = search(index);

        //中间插：
        //先绑后：
        //对于---> 方向
        node.next = cur;
        cur.prev.next = node;
        //对于 <--- 方向
        node.prev = cur.prev;
        cur.prev = node;
    }

    private ListNode<E> search(int index) {
        ListNode<E> cur = head;
        int count = index;
        while (count > 0) {
            cur = cur.next;
            count--;
        }
        return cur;
    }

    /**
     * 打印
     */
    public void display() {
        ListNode<E> cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 求长度
     * @return
     */
    public int size() {
        ListNode<E> cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 查找
     * @param key
     * @return
     */
    public boolean contains(E key) {
        ListNode<E> cur = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void removeKey(E key) {
        //情况1：链表是空的==>尾必要删除
        if (head == null) {
            return;
        }
        //链表不空
        ListNode<E> cur = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                if (cur == head) {
                    //情况2：头删
                    //头变新
                    head = head.next;
                    if (head == null) {//情况3：只有一个节点
                        last = null;
                    } else {
                        //新头无前驱
                        head.prev = null;
                    }
                } else if(cur == last){
                    //情况4：尾删
                    //尾变新
                    last = last.prev;
                    //新尾无后继
                    last.next = null;
                } else {
                    //情况5：中间删除
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                //程序走到这里：说明删除首次出现的key完毕，直接返回
                return;
            } else { //如果不一样:指针后移
                //走到这里
                cur = cur.next;//指针后移
            }
        }
    }

    /**
     * 删除所有关键字key
     * @param key
     */
    public void removeAllKey(E key) {
        //情况1：链表是空的==>尾必要删除
        if (head == null) {
            return;
        }
        //链表不空
        ListNode<E> cur = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                if (cur == head) {
                    //情况2：头删
                    //头变新
                    head = head.next;
                    if (head == null) {//情况3：只有一个节点
                        last = null;
                    } else {
                        //新头无前驱
                        head.prev = null;
                    }
                } else if(cur == last){
                    //情况4：尾删
                    //尾变新
                    last = last.prev;
                    //新尾无后继
                    last.next = null;
                } else {
                    //情况5：中间删除
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                //删除所有关键字key 让他一直循环遍历好了，不用返回
                /*return;*/
            }
            //每一次无论是否是key指针都后移指针后移
            cur = cur.next;
        }
    }
}
